package day002;

public class Code04_ReverseList {

    public static class Node{
        public int value;
        public Node next;

        public Node(int data){
            this.value = data;
        }
    }

    public static void printList(Node head){
        while(head != null){
            System.out.print(head.value+(head.next!=null ? "->" : "\n"));
            head = head.next;
        }
    }

    public static Node reverseList(Node head){

        //遍历数组
        Node cur = head;
        Node prev = null;
        Node nextTmp;

        while(cur != null){
            nextTmp = cur.next;

            cur.next = prev;
            prev = cur;
            cur = nextTmp;
        }
        return prev;
    }

    public static Node reverseList2(Node head){
        if(head == null || head.next == null){
            return head;
        }
        Node newHead = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static Node reverseList3(Node head){
        Node dummy = new Node(-1);
        dummy.next = head;
        Node cur = dummy.next, nextTmp;
        while(cur != null && cur.next != null){
            nextTmp = cur.next;
            cur.next = nextTmp.next;
            nextTmp.next = dummy.next;
            dummy.next = nextTmp;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        Node newHead = reverseList3(n1);
        printList(newHead);

    }
}
